package sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class ShellSort {

    public static void shellSort(int[] arr) {
        if(arr == null || arr.length <= 1){
            return;
        }
        int n = arr.length;
        for(int step = n/2; step >= 1; step = step/2){
            // 对每一组进行插入排序
            for(int i = step; i< n; i++){
                int temp = arr[i];
                int insertIndex = i-step;
                while (insertIndex>=0 && arr[insertIndex] > temp){
                    arr[insertIndex + step] = arr[insertIndex];
                    insertIndex = insertIndex - step;
                }
                arr[insertIndex + step] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
//        selectionSort(arr);
        shellSort(arr);
        System.out.println(Arrays.stream(arr).boxed().collect(Collectors.toList()));
    }
}
